{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Absolute Differences in a Sorted Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getSumAbsoluteDifferences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有序数组中差绝对值之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>非递减 </strong>有序整数数组 <code>nums</code> 。</p>\n",
    "\n",
    "<p>请你建立并返回一个整数数组<em> </em><code>result</code>，它跟<em> </em><code>nums</code> 长度相同，且<code>result[i]</code> 等于<em> </em><code>nums[i]</code> 与数组中所有其他元素差的绝对值之和。</p>\n",
    "\n",
    "<p>换句话说， <code>result[i]</code> 等于 <code>sum(|nums[i]-nums[j]|)</code> ，其中 <code>0 <= j < nums.length</code> 且 <code>j != i</code> （下标从 0 开始）。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,3,5]\n",
    "<b>输出：</b>[4,3,5]\n",
    "<b>解释：</b>假设数组下标从 0 开始，那么\n",
    "result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4，\n",
    "result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3，\n",
    "result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,4,6,8,10]\n",
    "<b>输出：</b>[24,15,13,15,21]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= nums[i] <= nums[i + 1] <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-absolute-differences-in-a-sorted-array](https://leetcode.cn/problems/sum-of-absolute-differences-in-a-sorted-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-absolute-differences-in-a-sorted-array](https://leetcode.cn/problems/sum-of-absolute-differences-in-a-sorted-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,5]', '[1,4,6,8,10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        prefix = [nums[0]]\n",
    "        for i in range(1, n):\n",
    "            prefix.append(prefix[-1] + nums[i])\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(len(nums)):\n",
    "            left_sum = prefix[i] - nums[i]\n",
    "            right_sum = prefix[-1] - prefix[i]\n",
    "            \n",
    "            left_count = i\n",
    "            right_count = n - 1 - i\n",
    "            \n",
    "            left_total = left_count * nums[i] - left_sum\n",
    "            right_total = right_sum - right_count * nums[i]\n",
    "\n",
    "            ans.append(left_total + right_total)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\r\n",
    "        length = len(nums)\r\n",
    "        p = 0\r\n",
    "        total_sum = sum(nums)\r\n",
    "        for i in range(length):\r\n",
    "            ps_sum = total_sum - 2*p - nums[i]\r\n",
    "            p += nums[i]\r\n",
    "            nums[i] = nums[i] * (2*i+1-length) + ps_sum\r\n",
    "        return nums\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        l = len(nums)\n",
    "        res = [0] * l\n",
    "        r = 0\n",
    "        for i in range(1,l):\n",
    "            r += nums[i] - nums[0]\n",
    "        res[0] = r\n",
    "        for i in range(1,l):\n",
    "            dt = nums[i] - nums[i-1]\n",
    "            if dt == 0:\n",
    "                res[i] = r\n",
    "                continue\n",
    "            # print(i,dt,i,l-i)\n",
    "            r = r + (i) * dt - (l-i) * dt\n",
    "            res[i] = r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        result=[]       \n",
    "        for i in range(len(nums)):\n",
    "            if i!=0 and nums[i]==nums[i-1]:\n",
    "                result.append(s)\n",
    "                s1+=nums[i-1]\n",
    "                s2-=nums[i-1]\n",
    "            else:\n",
    "                s = 0\n",
    "                if i==0:\n",
    "                    s1=0\n",
    "                    s2=sum(nums)\n",
    "                else:\n",
    "                    s1+=nums[i-1]\n",
    "                    s2-=nums[i-1]\n",
    "                \n",
    "                s=i*nums[i]-s1+s2-(len(nums)-i)*nums[i]\n",
    "                result.append(s)\n",
    "        return(result)        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        result = [0]\n",
    "        for i in nums:\n",
    "            result[0] += abs(i-nums[0])\n",
    "        L=R=1\n",
    "        for j in range(1,len(nums),1):\n",
    "            if nums[j]==nums[j-1] or R ==1:\n",
    "                R += 1\n",
    "            else:\n",
    "                result+=[result[L-1]+(nums[L]-nums[L-1])*(L-len(nums)+L)]*(R-L)\n",
    "                L=R\n",
    "                R += 1\n",
    "        result+=[result[L-1]+(nums[L]-nums[L-1])*(L-len(nums)+L)]*(R-L)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        arr = sorted(nums)\n",
    "        l = 0\n",
    "        r = sum(arr)\n",
    "        n = len(arr)\n",
    "        \n",
    "        mem = {}                             \n",
    "        \n",
    "        for i,num in enumerate(arr):\n",
    "            l += num\n",
    "            r -= num\n",
    "            if num not in mem:\n",
    "                mem[num] = (i+1)*num-l + r-(n-i-1)*num\n",
    "        \n",
    "        # print(arr)\n",
    "        # print(mem)\n",
    "                  \n",
    "        res = []\n",
    "        for num in nums:\n",
    "            res.append(mem[num])\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        pre = [0]\n",
    "        for num in nums:\n",
    "            pre.append(pre[-1] + num)\n",
    "        for i, num in enumerate(nums):\n",
    "            nums[i] = num * i - pre[i] - num * (len(nums) - i - 1) + pre[-1] - pre[i + 1]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        sumd=len(nums)\n",
    "        cnt=Counter(nums)\n",
    "        nums1=list(set(nums))\n",
    "        nums1.sort()\n",
    "        leftsum=[nums[0]*cnt[nums[0]]]\n",
    "        rightsum=[nums[-1]*cnt[nums[-1]]]\n",
    "        for i in range(1,len(nums1)):\n",
    "            leftsum.append(leftsum[-1]+nums1[i]*cnt[nums1[i]])\n",
    "            rightsum=[rightsum[0]+nums1[-i-1]*cnt[nums1[-i-1]]]+rightsum\n",
    "        leftsum=[0]+leftsum\n",
    "        rightsum.append(0)\n",
    "\n",
    "        re=[]\n",
    "        numd=0\n",
    "        left=0\n",
    "\n",
    "        for i in range(len(nums1)):\n",
    "            numd=-leftsum[i]+rightsum[i]+(2*left-sumd)*nums1[i] #(cnt[nums1[i]]+left-(sumd-left-cnt[nums1[i]]))\n",
    "            left+=cnt[nums1[i]]\n",
    "            for _ in range(cnt[nums1[i]]):\n",
    "                re.append(numd)\n",
    "        return re\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        ret = [0] * len(nums)\n",
    "\n",
    "        lo = 0\n",
    "        hi = sum(nums)\n",
    "\n",
    "        for i, n in enumerate(nums):\n",
    "            lo += n\n",
    "            hi -= n\n",
    "            # print(i, n, lo, hi)\n",
    "            ret[i] = (n * (i + 1) - lo) + (hi - n * (len(nums) - i - 1))\n",
    "            \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        sr = sum(nums)\n",
    "        sl = 0\n",
    "        for i in range(0, len(nums)):\n",
    "            ans.append(i * nums[i] - sl + sr - (len(nums) - i) * nums[i])\n",
    "            sl += nums[i]\n",
    "            sr -= nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        result = [0] * n\n",
    "        result[0] = sum(nums) - nums[0] * n\n",
    "        for i in range(1, n):\n",
    "            d = nums[i] - nums[i - 1]\n",
    "            result[i] = result[i - 1] - (n - i * 2) * d\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [0] * n\n",
    "        for i in range(n):\n",
    "            res[0] += (nums[i] - nums[0])\n",
    "        for i in range(1,n):\n",
    "            res[i] = res[i-1] + (nums[i] - nums[i-1]) * (2*i - n)\n",
    "        return res           \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        ret = [0] * n\n",
    "        difflist=[]\n",
    "        # if n==1:\n",
    "        #     return [0]\n",
    "        for i in range(1,n):\n",
    "            difflist.append(nums[i]-nums[i-1])\n",
    "        print(difflist)\n",
    "\n",
    "        for j in range(0,n-1):\n",
    "            ret[0]+=(n-j-1)*difflist[j]\n",
    "        for i in range(1,n):\n",
    "            ret[i]=ret[i-1]+(2*i-n)*difflist[i-1]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        postfix = [0] * (n+1)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            postfix[i] = postfix[i+1] + nums[i]\n",
    "        \n",
    "        prefix = 0\n",
    "        for i in range(n):\n",
    "            prefix, nums[i] = prefix+nums[i], (2 * i + 1 - n) *nums[i] - prefix + postfix[i+1]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "# 前缀和\n",
    "# class Solution:\n",
    "#     def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "#         n = len(nums)\n",
    "#         if n == 1:\n",
    "#             return [0]\n",
    "#         ans = [0] * n\n",
    "#         preSum = [0] * (n + 1)\n",
    "#         for i in range(n):\n",
    "#             preSum[i + 1] = preSum[i] + nums[i]\n",
    "#         for i in range(0, n):\n",
    "#             num = nums[i]\n",
    "#             left = i * num - preSum[i]\n",
    "#             right = (preSum[n] - preSum[i + 1]) - (n - i - 1) * num\n",
    "#             ans[i] = left + right\n",
    "#         return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        s = sum(num - nums[0] for num in nums)\n",
    "        ans[0] = s\n",
    "        for i in range(1, n):\n",
    "            s += i * (nums[i] - nums[i - 1]) - (n - i) * (nums[i] - nums[i - 1])\n",
    "            ans[i] = s\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 在前缀和基础上考虑是否能通过一次遍历解决问题，right部分的前缀和用于解决d+e的值，这里我们可以考虑使用sum(nums)-prefix[i]获得d+e的值\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        acc, L = 0, len(nums)\n",
    "        s = sum(nums)\n",
    "        ret = []\n",
    "        for i, n in enumerate(nums):\n",
    "            left = i * n - acc\n",
    "            acc += n\n",
    "            right = s - acc - (L - 1 - i) * n\n",
    "            ret.append(left + right)\n",
    "        return ret\n",
    "\n",
    "# # 前缀和；假设nums=[a, b, c, d, e]，前缀和为[0, a, a+b, a+b+c, a+b+c+d, a+b+c+d+e]；由于nums为非递减数组，考虑result[2] = (c-a + c-b) + (e-c + d-c)，可以拆成左右两部分。左即为2*c-a-b，右为e+d-2*c。(a+b)以及(d+e)都可以通过前缀和很快算出。2可以通过下标计算获得。\n",
    "# from itertools import accumulate\n",
    "# class Solution:\n",
    "#     def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "#         prefix = list(accumulate(nums, initial=0))\n",
    "#         L = len(nums)\n",
    "#         ret = []\n",
    "#         for i, n in enumerate(nums):\n",
    "#             left = i * n - prefix[i]\n",
    "#             right = prefix[-1] - prefix[i+1] - (L - 1- i) * n\n",
    "#             ret.append(left + right)\n",
    "#         return ret\n",
    "\n",
    "# # 自己想的方法不是很好\n",
    "# class Solution:\n",
    "#     def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "#         n = len(nums)\n",
    "#         diffs = [b - a for a, b in zip(nums, nums[1:])]\n",
    "#         left = 0\n",
    "#         right = sum(diffs[i]*(n-1-i) for i in range(n-1))\n",
    "#         ret = [left + right]\n",
    "#         for i in range(1, n):\n",
    "#             left += diffs[i-1] * i\n",
    "#             right -= diffs[i-1] * (n-i)\n",
    "#             ret.append(left + right)\n",
    "#         return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n \n",
    "        dp[0] = sum(nums) - n * nums[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = dp[i-1] - (nums[i] - nums[i-1]) * (n - 2 * i)\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        diffs = [b - a for a, b in zip(nums, nums[1:])]\n",
    "        left = 0\n",
    "        right = sum(diffs[i]*(n-1-i) for i in range(n-1))\n",
    "        ret = [left + right]\n",
    "        for i in range(1, n):\n",
    "            left += diffs[i-1] * i\n",
    "            right -= diffs[i-1] * (n-i)\n",
    "            ret.append(left + right)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        result = [sum(num - nums[0] for num in nums)] + [0] * ((n := len(nums)) - 1)\n",
    "        for i in range(1, n):\n",
    "            result[i] = result[i - 1] + (nums[i] - nums[i - 1]) * ((i << 1) - n)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        presum = [0] + list(accumulate(nums))\n",
    "        res = []\n",
    "        for i, num in enumerate(nums):\n",
    "            l = num * i - presum[i]\n",
    "            r = (presum[-1] - presum[i + 1] - num * (len(nums) - i - 1))\n",
    "            res.append(l + r)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        pre = [0] * n\n",
    "        pre[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            pre[i] = pre[i - 1] + nums[i]\n",
    "        res = [0] * n\n",
    "        for i in range(n):\n",
    "            res[i] = nums[i] * (i + 1) - pre[i] + pre[n - 1] - pre[i] - nums[i] * (n - i - 1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        prefix = [0] * len(nums)\n",
    "        prefix[0] = nums[0]\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            prefix[i] = nums[i] + prefix[i - 1]\n",
    "\n",
    "        res = [0] * len(nums)\n",
    "\n",
    "        temp = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            temp += (nums[i] - nums[0])\n",
    "\n",
    "        res[0] = temp\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            res[i] = nums[i] * i - prefix[i - 1] + prefix[-1] - prefix[i] - (len(nums) - i - 1) * nums[i]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        presum = [0] + list(accumulate(nums))\n",
    "        res = []\n",
    "        for i, num in enumerate(nums):\n",
    "            l = num * i - presum[i]\n",
    "            r = (presum[-1] - presum[i + 1] - num * (len(nums) - i - 1))\n",
    "            res.append(l + r)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        m = n + 1\n",
    "        prefix_sum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            prefix_sum[i + 1] = prefix_sum[i] + nums[i]\n",
    "        tmp = 0\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            tmp += (nums[i] * (i + 1)) - prefix_sum[i + 1]\n",
    "            tmp += (prefix_sum[m - 1]) - prefix_sum[i + 1] - nums[i] * (n - i - 1)\n",
    "            ans.append(tmp)\n",
    "            tmp = 0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0]\n",
    "        for i in range(len(nums)):\n",
    "            ans.append(ans[-1]+nums[i])\n",
    "        print(ans)\n",
    "        res = [0] * len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            res[i] = (2 * i + 2 - len(nums)) * nums[i] - 2 * ans[i + 1] + ans[-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:\r\n",
    "        n = len(nums)\r\n",
    "        ans = [0] * n\r\n",
    "        # 前綴和\r\n",
    "        pre = [0] * n\r\n",
    "        for i in range(1, n):\r\n",
    "            pre[i] = pre[i-1] + nums[i-1]\r\n",
    "        # 後綴和\r\n",
    "        suf = [0] * n\r\n",
    "        for i in range(n-2, -1, -1):\r\n",
    "            suf[i] = suf[i+1] + nums[i+1]\r\n",
    "        # 計算答案\r\n",
    "        for i in range(n):\r\n",
    "            p = nums[i] * i - pre[i]\r\n",
    "            s = suf[i] - nums[i] * (n-i-1)\r\n",
    "            ans[i] = p + s\r\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
